package com.tgy.链表;

/***
 * @ClassName: Josefu
 * @Description: 单项循环链表解决约瑟夫环问题
 * @Auther: tanggy3
 * @Date: 16:39 2022/7/27
 * @version : V1.0
 */
public class Josefu {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.add(5);
        list.show();
        list.countBoy(1,2,5);

    }
}

/**
 * 创建一个环形单项链表
 */
class CircleSingleLinkedList {
    //创建一个first节点，当前没有编号
    private Node first = null;

    public CircleSingleLinkedList() {
    }

    /**
     * 添加节点 nums为需要添加的节点
     */
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("输入值不正确");
            return;
        }
        Node curNode = null;//辅助指针，帮助构建环形链表
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i);
            //如果是第一个
            if (i == 1) {
                first = node;
                first.nextNode = first;//构成环
                curNode = node;
            } else {
                curNode.nextNode = node;
                node.nextNode = first;//构成环
                curNode = node;//把辅助变量设置到最后变量
            }
        }
    }

    /**
     * 展示环形链表
     */
    public void show() {
        //判空
        if (first == null) {
            System.out.println("空");
            return;
        }
        ;
        //因为first不能动，所以需要一个辅助节点来帮助遍历节点
        Node curNode = first;
        while (true) {
            System.out.printf("节点编号为%d\n", curNode.no);
            if (curNode.nextNode == first) {
                break;
            }
            curNode = curNode.nextNode;
        }
    }

    /**
     * 根据用户输入，计算出圈顺序
     *
     * @param startNo 从第几个开始数
     * @param countNo 数几下
     * @param nums    表示有几个节点
     */
    public void countBoy(int startNo, int countNo, int nums) {
        //数据校验
        if (startNo > nums || startNo < 1 || first == null) {
            System.out.println("输入数据有误");
            return;
        }
        /**
         * 先让first移动到起始位置
         */
        while(true){
            if(first.no == startNo){break;}
            first = first.nextNode;
        }
        Node helper = first; //定义辅助节点，帮助删除节点
        //先让helper指向first的后一个
        while (true) {
            if (helper.nextNode == first) break;//说明hleper指向了最后一个节点
            helper = helper.nextNode;
        }

        /**
         * 出圈
         */
        while (true){
            if(helper == first) break;//说明最后一个节点
            //报数
            for (int i = 1; i < countNo; i++) {//需要少移动一次定位到需要出圈的节点上
                first = first.nextNode;
                helper = helper.nextNode;
            }
            System.out.printf("节点%d出圈\n",first.no);
            first = first.nextNode;//将first指向要删除节点的后一个，否则first就消失了，失效了
            helper.nextNode = first;
        }
        System.out.printf("最后一个节点%d出圈\n",first.no);

    }

}


